🚀 สถานการณ์

ห่วงโซ่อุปทานวุ่นวาย 📉

เรือมาถึงในลำดับที่สับสน เราต้องคำนวณค่าความวุ่นวาย (จำนวนการกลับด้าน) เพื่อปรับปรุงระบบควบคุมจราจรโดยปัญญาประดิษฐ์ ค่าความวุ่นวาย (จำนวนการกลับด้าน) เพื่อปรับปรุงระบบควบคุมจราจรโดยปัญญาประดิษฐ์

การกลับด้านคืออะไร?

คู่ของดัชนี $(i, j)$ จะถือว่าเป็นการกลับด้าน ก็ต่อเมื่อ:

  • $i < j$ (เรือ $i$ มาถึงก่อน $j$)
  • $A[i] > A[j]$ (เรือ $i$ มีรหัสลำดับความสำคัญสูงกว่า)

การวิเคราะห์ 🔍

ลำดับตัวอย่าง: [2, 4, 1, 3, 5]

  • ❌ (2, 1): 2 มาถึงก่อน 1 แต่ 2 > 1
  • ❌ (4, 1): 4 มาถึงก่อน 1 แต่ 4 > 1
  • ❌ (4, 3): 4 มาถึงก่อน 3 แต่ 4 > 3
  • ความวุ่นวายรวม: 3 การกลับด้าน

ความท้าทาย

การใช้ลูปซ้อนแบบแรงงานตรง ๆ มีความซับซ้อนระดับ $O(N^2)$.

for i in range(n):
  for j in range(i+1, n): ...

สำหรับ $N=100,000$ กระบวนการนี้ใช้เวลาประมาณ 10 พันล้านรอบการทำงาน ผลลัพธ์: เกินเวลาที่กำหนด